using System;
using System.Collections;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0133. 克隆图")]
    public class No0133_CloneGraph : AbsBaseTestItem
    {
        public class Node
        {
            public int val;
            public IList<Node> neighbors;
            public Node()
            {
                val = 0;
                neighbors = new List<Node>();
            }
            public Node(int _val)
            {
                val = _val;
                neighbors = new List<Node>();
            }
            public Node(int _val, List<Node> _neighbors)
            {
                val = _val;
                neighbors = _neighbors;
            }
        }

        /*
        给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
        图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
        */

        public override void OnTest()
        {
        }

        public Node CloneGraph(Node node)
        {
            if (node == null) return null;
            Dictionary<int, Node> dic = new Dictionary<int, Node>();
            dic.Add(node.val, new Node(node.val, new List<Node>()));
            Queue queue = new Queue();
            queue.Enqueue(node);
            while (queue.Count > 0)
            {
                var temp = (Node)queue.Dequeue();
                foreach (var n in temp.neighbors)
                {
                    if (dic.ContainsKey(n.val) == false)
                    {
                        var nn = new Node(n.val, new List<Node>());
                        dic.Add(n.val, nn);
                        queue.Enqueue(n);
                    }
                    dic[temp.val].neighbors.Add(dic[n.val]);
                }
            }
            return dic[node.val];
        }
    }
}
